/**
 * Huffman 编码
*/
#include <stdlib.h>
#include <string.h>

#ifndef HUFFMAN_TREE
#define HUFFMAN_TREE

// Huffman 编码长度
#ifndef HuffmanCodeLength
#define HuffmanCodeLength 50
#endif

// Huffman 树节点
typedef struct HuffmanNode HuffmanNode;
struct HuffmanNode {
    //结点值
    char data[HuffmanCodeLength/5]; 
    char code[HuffmanCodeLength];
    // 权重 
    double weight;
};
#define TreeElementType HuffmanNode

#include "Tree.c"

// 使用堆来构建 Huffman，堆元素类型为树节点指针 TreeNode*
#define HeapElementType TreeNode*
#include "Heap.c"

HuffmanNode createHuffmanNode(char* data, double weight) {
    HuffmanNode node;
    if (data == NULL) {
        node.data[0] = 0;
    } else {
        strcpy(node.data, data);
    }
    node.code[0] = 0;
    node.weight = weight;
    return node;
}

TreeNode* createHuffmanFromMinHeap(Heap* minHeap) {
    for(int i=1, len = minHeap->size; i < len; i++) {
        Tree left = deleteHeap(minHeap);
        Tree right = deleteHeap(minHeap);
        HuffmanNode hfNode = createHuffmanNode(NULL, left->data.weight + right->data.weight);
        TreeNode* node = createTreeNode(hfNode);
        node->left = left;
        node->right = right;
        insertHeap(minHeap, node);
    }
    return deleteHeap(minHeap);
}

//计算最优编码长度Weighted Path Length
int calHuffmanWPL(Tree hf, int depth){  // Depth从0开始
    if(hf->left == NULL && hf->right == NULL)
        return (depth * hf->data.weight);
    else{ // 有左右孩子,WPL= 左WPL+右WPL
        return calHuffmanWPL(hf->left, depth+1) + calHuffmanWPL(hf->right, depth+1);
    }
}

// 计算 Huffman 编码
void calHuffmanCode(Tree hf) {
    if (hf->left != NULL) {
        strcpy(hf->left->data.code, hf->data.code);
        strcat(hf->left->data.code, "0");
        calHuffmanCode(hf->left);
    } 
    if (hf->right != NULL) {
        strcpy(hf->right->data.code, hf->data.code);
        strcat(hf->right->data.code, "1");
        calHuffmanCode(hf->right);
    }
}

// 输出 Huffman 编码
void visitTreeNode(TreeNode* treeNode) {
    HuffmanNode node = treeNode->data;
    if (strlen(node.data) > 0) {
        printf("%s(%3.1f): %s\n", node.data, node.weight, node.code);
    }
}

#endif
